In [Timofte 2013], Anchored Nearest-Neighbor Regression (ANR) is proposed for fast and accurate Super-Resolution. Even though the proposed algorithm greatly speeds-up former patch regression approaches like [Yang 2010], it still requires (1) efficiently determining the nearest anchored regressor and (2) computing the regression for all pixels in each overlapping patch and then linearly combining the contributions from overlapping patches. For determining the nearest anchored regressor, a linear search is suggested.
In [Yang 2013], In-place Example Regression (IER) is proposed for combining classical techniques from single-image super resolution with trained regressor priors. [Yang2013] views the patch-based single image super-resolution problem as a regression problem, i.e. finding a mapping function ƒ from the low-resolution patch space to the target high-resolution patch space. Even though the authors seem to indicate they do not need to perform a search for suitable cross-scale similar examples, an in-depth analysis of the algorithm shows that a small search window of size 3×3 is still required to find the most suitable cross-scale example. Further, the disclosed algorithm still requires computing the IER for overlapping patches and linearly combining the overlapping computed contributions. Furthermore, this technique requires an iterative application with small magnification factor to correctly exploit the cross-scale prior.
The above-described ANR and IER approaches have some drawbacks. The drawbacks comprise at least that (1) it is inefficient to determine the regressor for each contribution, (2) block matching is required for finding cross-scale nearest neighbors, (3) computations are redundant when done for all pixels in each patch, whereby it needs to be kept in mind that pixels distant from the center of a patch will generally show poor regression performance, and (4) only small magnification factors can be achieved, or multiple steps are required to estimate the super-resolved image for larger magnification factors, such as e.g. 3×.
Binary partition trees are well-known data structures for fast data retrieval, among other applications.